package 链表.middle;

/**
 * 设计链表
 * @author Lw中
 * @date 2020/9/21 10:17
 */
public class QiLingQi {

    /**
     * 头结点
     */
    private Node header;
    /**
     * 尾节点
     */
    private Node tail;
    /**
     * 节点个数
     */
    private int size;

    /**
     * 链表节点
     */
    private static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    /**
     * 构造方法：初始化链表
     */
    public QiLingQi() {
        // 头结点为空
        header = null;
        // 尾节点为空
        tail = null;
        size = 0;
    }

    /**
     * 通过index获取第index个节点，如果index超出范围返回-1
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        //		获取头节点
        Node temp = header;
//		从头节点开始遍历到index位置之前的节点
        for (int i = 0; i < index; i++) {
//			将index-1的下一个位置的index位置的节点充斥着临时节点
            temp = temp.next;
        }
        //返回index位置节点
        return temp.data;
    }

    /**
     * 查找结点
     *
     * @param index 节点位置
     */
    public Node getNode(int index) throws Exception {
        if (index<0 || index>=size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
//		获取头节点
        Node temp = header;
//		从头节点开始遍历到index位置之前的节点
        for(int i=0; i<index; i++) {
//			将index-1的下一个位置的index位置的节点充斥着临时节点
            temp = temp.next;
        }
//		返回index位置节点
        return temp;
    }


    /**
     * 头插法：将节点插入在第一个位置
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /**
     * 尾插法：将节点添加在末尾
     */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /**
     * 将节点添加在index位置
     */
    public void addAtIndex(int index, int val) {
        if (index<0 || index>size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
//		通过传入的节点数据初始化节点
        Node insertNewNode = new Node(val);
//		空链表插入
        if (size==0) {
//			空链表
//			若链表为空将新插入的节点存储在头结点和尾节点上
            header = insertNewNode;
            tail = insertNewNode;
        } else if(index==0) {
//			插入头部
//			第一步：把要插入的节点的next指向head
//			第二步：将要插入的节点存储在头结点上
            insertNewNode.next = header;
            header = insertNewNode;
        } else if(index==size) {
//			插入尾部
//			第一步：将尾节点的next指向需要插入的节点
//			第二步：将要插入的节点存储在尾节点上
            tail.next = insertNewNode;
            tail = insertNewNode;
        } else {
//			插入中间
//			第一步：获取index-1位置的节点
//			第二步：将insertNewNode的next指向index+1(preNode.next)位置的节点
//			第三步：将index-1位置的节点的next(preNode.next)指向insertNewNode
            Node preNode = null;
            try {
                preNode = getNode(index-1);
            } catch (Exception e) {
                e.printStackTrace();
            }
            insertNewNode.next = preNode.next;
            preNode.next = insertNewNode;
        }
        size++;
    }

    /**
     * 将index位置的节点删除
     */
    public void deleteAtIndex(int index) {
        if (index<0 || index>=size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node deleteNode = null;
        if(index==0) {
//			删除头结点
//			第一步：将头节点存储在新创的deleteNode中
//			第二步：将头结点的下一个结点存储在头结点上
            deleteNode = header;
            header = header.next;
        } else if(index==size-1) {
//			删除尾节点
//			第一步：获取要删除的节点的前一个结点(preNode)
//			第二步：将preNod的next指向null
//			第三步：将preNode存储到last结点
            Node preNode = null;
            try {
                preNode = getNode(index-1);
            } catch (Exception e) {
                e.printStackTrace();
            }
            deleteNode = preNode.next;
            preNode.next = null;
            tail = preNode;
        } else {
//			删除中间节点
//			第一步：遍历获取要删除节点的前一个结点
//			第二步：将要删除的节点的前一个节点的next指向index+1位置的结点
            Node preNdoe = null;
            try {
                preNdoe = getNode(index-1);
            } catch (Exception e) {
                e.printStackTrace();
            }
            Node nextNode = preNdoe.next.next;
            deleteNode = preNdoe.next;
            preNdoe.next = nextNode;
        }
        size--;
    }

    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList obj = new MyLinkedList();
     * int param_1 = obj.get(index);
     * obj.addAtHead(val);
     * obj.addAtTail(val);
     * obj.addAtIndex(index,val);
     * obj.deleteAtIndex(index);
     */

    /**
     * 输出链表
     */
    public void output() {
        Node temp = header;
        while(temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {

        QiLingQi linkedList = new QiLingQi();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1,2);
        linkedList.get(1);
        linkedList.deleteAtIndex(1);
        linkedList.get(1);
        linkedList.output();
    }

}
